package lc20240423;

import java.util.Arrays;

public class HIndex {
    public static void main(String[] args) {
        int[] citations={3,0,6,1,5,7};

        System.out.println(hIndex1(citations));
    }
    public static int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }

    public static int hIndex1(int[] citations) {
        //采用二分查找的方法。
        Arrays.sort(citations);
        int left=0;
        int right=citations.length-1;
        int h=0;
        //这里left<=right，是因为有可能指向同一个元素。
        while (left<=right){
            int mid=left+(right-left)/2;
            //判断当前mid元素是否大于等于数组长度-mid下标。如果用最后一个下标减去mid则会少1。
            if (citations[mid]>=citations.length-mid){
                h= citations.length-mid;
                //继续往左寻找是否有元素满足要求。
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return h;
    }
}
